% This is "sig-alternate.tex" V2.0 May 2012
% This file should be compiled with V2.5 of "sig-alternate.cls" May 2012
%
% This example file demonstrates the use of the 'sig-alternate.cls'
% V2.5 LaTeX2e document class file. It is for those submitting
% articles to ACM Conference Proceedings WHO DO NOT WISH TO
% STRICTLY ADHERE TO THE SIGS (PUBS-BOARD-ENDORSED) STYLE.
% The 'sig-alternate.cls' file will produce a similar-looking,
% albeit, 'tighter' paper resulting in, invariably, fewer pages.
%
% ----------------------------------------------------------------------------------------------------------------
% This .tex file (and associated .cls V2.5) produces:
%       1) The Permission Statement
%       2) The Conference (location) Info information
%       3) The Copyright Line with ACM data
%       4) NO page numbers
%
% as against the acm_proc_article-sp.cls file which
% DOES NOT produce 1) thru' 3) above.
%
% Using 'sig-alternate.cls' you have control, however, from within
% the source .tex file, over both the CopyrightYear
% (defaulted to 200X) and the ACM Copyright Data
% (defaulted to X-XXXXX-XX-X/XX/XX).
% e.g.
% \CopyrightYear{2007} will cause 2007 to appear in the copyright line.
% \crdata{0-12345-67-8/90/12} will cause 0-12345-67-8/90/12 to appear in the copyright line.
%
% ---------------------------------------------------------------------------------------------------------------
% This .tex source is an example which *does* use
% the .bib file (from which the .bbl file % is produced).
% REMEMBER HOWEVER: After having produced the .bbl file,
% and prior to final submission, you *NEED* to 'insert'
% your .bbl file into your source .tex file so as to provide
% ONE 'self-contained' source file.
%
% ================= IF YOU HAVE QUESTIONS =======================
% Questions regarding the SIGS styles, SIGS policies and
% procedures, Conferences etc. should be sent to
% Adrienne Griscti (griscti@acm.org)
%
% Technical questions _only_ to
% Gerald Murray (murray@hq.acm.org)
% ===============================================================
%
% For tracking purposes - this is V2.0 - May 2012

\documentclass{sig-alternate}
\newcommand{\Expect}{{\rm I\kern-.3em E}}

\begin{document}
%
% --- Author Metadata here ---
\conferenceinfo{ISLPED}{'14 La Jolla, CA USA}
\CopyrightYear{2013} % Allows default copyright year (20XX) to be over-ridden - IF NEED BE.
%\crdata{0-12345-67-8/90/01}  % Allows default copyright data (0-89791-88-6/97/05) to be over-ridden - IF NEED BE.
% --- End of Author Metadata ---

\title{Accurately Rounded Truncated Multipliers}
%\subtitle{[Extended Abstract]
%\titlenote{A full version of this paper is available as
%\textit{Author's Guide to Preparing ACM SIG Proceedings Using
%\LaTeX$2_\epsilon$\ and BibTeX} at
%\texttt{www.acm.org/eaddress.htm}}}
%
% You need the command \numberofauthors to handle the 'placement
% and alignment' of the authors beneath the title.
%
% For aesthetic reasons, we recommend 'three authors at a time'
% i.e. three 'name/affiliation blocks' be placed beneath the title.
%
% NOTE: You are NOT restricted in how many 'rows' of
% "name/affiliations" may appear. We just ask that you restrict
% the number of 'columns' to three.
%
% Because of the available 'opening page real-estate'
% we ask you to refrain from putting more than six authors
% (two rows with three columns) beneath the article title.
% More than six makes the first-page appear very cluttered indeed.
%
% Use the \alignauthor commands to handle the names
% and affiliations for an 'aesthetic maximum' of six authors.
% Add names, affiliations, addresses for
% the seventh etc. author(s) as the argument for the
% \additionalauthors command.
% These 'additional authors' will be output/set for you
% without further effort on your part as the last section in
% the body of your article BEFORE References or any Appendices.

\numberofauthors{1} %  in this sample file, there are a *total*
% of EIGHT authors. SIX appear on the 'first-page' (for formatting
% reasons) and the remaining two appear in the \additionalauthors section.
%
\author{
% You can go ahead and credit any number of authors here,
% e.g. one 'row of three' or two rows (consisting of one row of three
% and a second row of one, two or three).
%
% The command \alignauthor (no curly braces needed) should
% precede each author name, affiliation/snail-mail address and
% e-mail address. Additionally, tag each line of
% affiliation/address with \affaddr, and tag the
% e-mail address with \email.
%
% 1st. author
\alignauthor
Tuan D. Nguyen and James E. Stine\\
       \affaddr{VLSI Computer Architecture Research Group}\\
       \affaddr{Electrical and Computer Engineering Department}\\
       \affaddr{Oklahoma State University, OK 74075}\\
       \email{\{tuan.d.nguyen, james.stine\}@okstate.edu}
}
% There's nothing stopping you putting the seventh, eighth, etc.
% author on the opening page (as the 'third row') but we ask,
% for aesthetic reasons that you place these 'additional authors'
% in the \additional authors block, viz.
%\additionalauthors{Additional authors: John Smith (The Th{\o}rv{\"a}ld Group,
%email: {\texttt{jsmith@affiliation.org}}) and Julius P.~Kumquat
%(The Kumquat Consortium, email: {\texttt{jpkumquat@consortium.net}}).}
%\date{30 July 1999}
% Just remember to make sure that the TOTAL number of authors
% is the number that will appear on the first page PLUS the
% number that will appear in the \additionalauthors section.

\maketitle
\begin{abstract}

The truncated multipliers problem has been researched for a long time. However, most of contributions so far made an assumption that inputs (multiplicand and multiplier) are distributed uniformly; which is, in our opinion, not correct or too tight in many cases in reality. In fact, when the input distribution is known but not uniform, or unknown, available methods can not be applied. Therefore, it is necessary to have a new approach which have ability to deal with some uncertainties in input. In this paper, we propose the minimax approach to solve that. Some experimental results are also included to compare with other methos.
\end{abstract}

% A category with the (minimum) three required fields
%\category{H.4}{Information Systems Applications}{Miscellaneous}
%A category including the fourth, optional field follows...
%\category{D.2.8}{Software Engineering}{Metrics}[complexity measures, performance measures]

%\terms{Truncated Multipliers, Multiplication, Minimax, Optimization}

\keywords{Truncated Multipliers, Multiplication, Minimax, Optimization}

\section{Introduction}

High-speed parallel multipliers are fundamental building blocks in digital signal processing (DSP) systems \cite{ma:1990}. In many cases, parallel multipliers contribute a large part of these systems. As a result, improvement in multipliers can lead to significant improvment in DSP systems. 

A typical case of multiplication in many DSP systems is the fixed-width multiplication, where both input and output are fixed-width numbers. In these systems, the 2n products produced by the parallel multipliers are rounded to n bits to avoid growth in word size. As presented in \cite{lim:1992}, truncated multiplication provides an efficient method for reducing the hardware requirements of rounded parallel multipliers. With truncated multiplication, only the n+k most significant columns of the multiplication matrix are used to compute the product. The error produced by omitting the 2n-k least significant columns and rounding the final result to n bits is estimated, and this estimate is added along with the n+k most significant columns to produce the rounded product. Although this leads to additional error in the rounded product, various techniques have been developed to help limit this error \cite{king:1997}, \cite{schulte:1993}, \cite{stine:2003}.

However, as far as we knew, all current contributions based on the assumption that the probability of inputs are uniform (each bit of inputs are assumed having equally probability between 0 and 1). We believe that this assumption is too tight and in many cases, is not guaranteed. Therefore, in this paper first we propose the solution for the cases where the input distribution is arbitrary known distribution or unknown but belong to a class of distribution by using minimax approach.

The paper is organized as follow: Section II summaries the state of the art in truncated multipliers, Section III states the problem in some uncertainties. Section IV includes some solutions for problems pointed out in Section III. Section V reports the experimental results and some discussions are included in Section VI. Finally, Section VII is the conclusion and future works. 

\section{Truncated Multipliers}
A Truncated Multipliers is a system that get two inputs $(A, B)$ and produce output $\hat{Z} = A \cdot B$ as shown in Figure \ref{fig:tm}. 
\begin{figure}[hbtp]
\centering
\includegraphics[scale=0.5]{tm.png}
\caption{Truncated Multipliers}
\label{fig:tm}
\end{figure}

For convenience, we assume that an unsigned n-bit multiplicand A is multiplied by an unsigned n-bit multiplier B to produce an unsigned 2n-bit product Z. Figure \ref{fig:44matrix} show an example with 4x4 multiplication matrix. For fractional numbers, the values for A, B and Z are:

\begin{figure}[hbtp]
\centering
\includegraphics[scale=0.5]{mul.png}
\caption{4x4 Multiplication Matrix}
\label{fig:44matrix}
\end{figure}

\[
A = \sum_{i=0}^{n-1}{a_i \cdot 2^{-n+i}} \hspace{1 cm} B = \sum_{j=0}^{n-1}{b_j \cdot 2^{-n+j}}\\
\]
\[
Z = A \cdot B = \sum_{i=0}^{n-1}\sum_{j=0}^{n-1} (a_i \cdot b_j) \cdot 2 ^{-2n+i+j} =  \sum_{k=0}^{2n-1} {\pi_k \cdot 2^{-2n+k}}
\]





The \textbf{full multipliers} first compute all $n^2$ partial products (PP) $\pi_{ij} = a_i \cdot b_j$, then summation of weighted PP to form double precision product and then add a 1 at the $n^{th}$ least significant bit position of the product and finally truncate the least significant n bits of the 2n bit sum \cite{swartzlander:1999}:
\[
\hat{Z}_{fm} = \left\lfloor \sum_{k=0}^{2n-1} {\pi_k \cdot 2^{-2n+k}} + \frac{ulp}{2•} \right\rfloor_n
\]
in which, $\left \lfloor \cdot \right\rfloor_n$ is the rounding down to n bit function and $ulp = 2^{-n}$.

This method, in one hand, guarantee that the absolute error is not larger than 0.5 ulp (unit in the last place), in the other hand, have to pay off by complexity, area, power consumption. In applications where only the single-precision product is required, we don't need to compute the least significant part of the product exactly as originally proposed by Lim in \cite{lim:1992}. It named truncated multipliers/multiplication or single-precision or fixed-width multipliers.

In \textbf{truncated multipliers}, only the $(n+k)$ most significant columns of the multiplication matrix are used to compute the product. Figure \ref{fig:44truncatedmatrix} shows an example of 4x4 bits.

\[
\hat{Z}_t  =  \left\lfloor \sum_{i+j = n-k}^{i+j = 2n-1} {(a_i \cdot b_j) \cdot 2 ^{-2n+i+j}}\right\rfloor_n 
\]

The error produced by omitting the $(n-k)$ least significant columns (reduction error) and rouding the final result to n bits (rounding error) is estimated, and this estimated is added along with the $(n+k)$ most significant columns to produce the rounded product.  
\begin{eqnarray*}
E_{total} & = & \left |{\hat{Z} - Z}\right| =  E_{reduction} + E_{roudning}\\
E_{reduction} & = & \left |{Z - \sum_{i+j = n-k}^{i+j = 2n-1} {(a_i \cdot b_j) \cdot 2 ^{-2n+i+j}}}\right| \\
E_{rounding} & = & \left| \sum_{i+j = n-k}^{i+j = 2n-1} {(a_i \cdot b_j) \cdot 2 ^{-2n+i+j}} - \hat{Z}_t\right| \\
\end{eqnarray*}

Various techniques have been developed to improve this estimation and reduce the total error \cite{lim:1992}\cite{stine:2003}. They did that by adding correction values to truncated summation before rounding it to n bits number.
\begin{figure}[hbtp]
\centering
\includegraphics[scale=0.5]{44matrix.png}
\caption{4x4 Truncated Multiplication Matrix}
\label{fig:44truncatedmatrix}
\end{figure}

\[
\hat{Z}_c  =  \left\lfloor \sum_{i+j = n-k}^{i+j = 2n-1} {(a_i \cdot b_j) \cdot 2 ^{-2n+i+j}} + \text{\textbf{C}}\right\rfloor_n 
\]



In \cite{lim:1992}, Lim proposed that correction value \textbf{C} (which he named fixed bias correction) should be the expectation (average) of truncated columns with an assumption that all PPs are i.r.v (independent random variable) with uniform distribution. In fact, Lim's correction value \textbf{C} equals to the expectation of reduction error:
\[
\textbf{C} = \Expect{[E_{reduction}]} = \frac{1}{4} \sum_{q=0}^{n-1}(q+1)\cdot 2^{-2n+q}
\]

Lim's ideas then were improved by Schulte and Swartzlander\cite{schulte:1993} by considering not only reduction error but also rounding error when computing correction value \textbf{C}. To estimate the expected value of the rounding error, it is also assumed that the distribution of any product bit $p_k$ is uniform. Moreover, Schulte and Swartzlander also suggest that \textbf{C} should be rounded to $(n+k)$ bits.

\[
\textbf{C}= \Biggl\lfloor \Expect{[E_{total}]}\Biggr\rfloor_{(n+k)} = \Biggl\lfloor \Expect{[E_{reduction} + E_{rounding}]}\Biggr\rfloor_{(n+k)}
\]
A method named data-dependent truncation then was proposed by King and Swartzlander\cite{king:1997}. In previous contribution, \textbf{C} is constant and  independent from data (inputs). With data-dependent truncation, the values of the PPs in column $(n-k-1)$ are used to estimate the error due to cut off the $(n-k)$ least significant columns. This is accomplished by adding the PP in column $(n-k-1)$ to column $(n-k)$. To compensate for the rounding error, a constant is added to columns $2n-2$ to $2n-k$ of the multiplication matrix.

\[
\textbf{C} = \left\lfloor \sum_{i,j}^{i+j = (n-k-1)} (a_i \cdot b_j) \cdot 2^{-2n + (n-k-1) + 1} + \Expect{[E_{rounding}]} \right\rfloor_{n+k}
\]

In \cite{stine:2003}, Stine and Duverne proposed a new method named hybrid truncated multipliers, in which, combines both the constant and variable correction methods. They introduced a new parameter p, which represents the percentage of variable correction to use for the correction. The calculation of the number of variable correction bits is the following utilizing the number of bits used in the variable correction method, $N_{variable}$:

\[
N_{hybrid} = floor( N_{variable} \cdot p )
\]

Hybrid method still uses a correction constant to compensate for the rounding error. However, a new correction constant based on the difference between the new varibale correction constant and the constant correction constant, as following:
\[
C_{VCT'} = 2^{-2n-k-2} \cdot N_{hybrid}
\]
\[
C_{round} = \Biggl\lfloor C_{CCT} - C_{VCT'} \Biggr\rfloor_{(n+k)}
\]

In \cite{petra:2010}\cite{decaro:2013}, authors use optimization approach to truncated multipliers. The decision variable is the correction value; which is considered a function of the $(n+k+1)^{th}$ column (which is named IC - input correction vector). The objection function is the mean square error or maximum absolute error.

\section{Truncated Multipliers Problem under some Uncertainties}

Implicitly or explicitly, all methods so far has assumed that the input distribution is uniform. Their results, hence, are meaningful when the assumption is true. But in reality, many cases, we can not guarantee that every inputs have the same probability. Moreover, in many cases, we even can not guarantee that the input distribution are known to the designer. Hereby we list some cases in which, the current approaches are not applicable:

\newdef{case}{Case}
\begin{case}
Inputs distribution is a known but arbitrary distribution: $(A, B) \sim P_0 (A, B)$
\end{case}
\begin{case}
Inputs distribution belongs to a discrete finite set of distribution with known prior:

\[
(A,B) \sim P(A,B) \in \{P_1 (A, B), P_2(A,B),..., P_k(A,B)\}
\]

in which, $P(P_i) = \pi_i$ known to the designer.
\end{case}

\begin{case}
Inputs distribution belongs to a discrete set of distribution with unknown prior:

\[
(A,B) \sim P(A,B) \in \{P_1 (A, B), P_2(A,B),..., P_k(A,B)\}
\]

in which, $P(P_i) = \pi_i$ unknown to the designer.
\end{case}

\begin{case}
Inputs distribution belongs to a set of infinite distribution with unknow prior:

\[
(A,B) \sim P(A,B) \in \mathbb{P}
\]

in which, $\mathbb{P}$ is some arbitrary set of distribution.
\end{case}

\section{Accurately Rounded Truncated Multipliers under some Uncertainties}
\subsection{Case 1: Truncated Multipliers with known arbitrary distribution}
\subsection{Case 2: Truncated Multipliers with known prior set of disbitrution}
\subsection{Case 3: Truncated Multipliers with unknown prior set of distribution}
\subsection{Case 4: Truncated Multipliers with arbitrary set of distribution}

%\subsection{Truncated Multipliers with unknown distribution}
%In practice, many cases the inputs distribution F are unknown to the truncated multipliers designers. This is the case that previous methods didn't solve and therefore, can lead to the unexpected results. For example, assuming that, given the distribution F, we can find a correction value f that minimize the expected error. But if the distribution changed, we can end up with the worst error. To deal with unknown prior knowledge of input, there's a effective approach named Minimax approach that we will briefly introduce as following.
%
%
%\subsubsection{Robust Truncated Multipliers}
%In the problem of truncated multipliers, H is the set of correction value $f \in R$, P is the set of all possible distribution in area $[0,1) \times [0,1)$. The cost function natually is the expected value of error due to truncation. We use sum notation because this is discrete-time signals.
%\begin{equation}
%M(h, p) = E_p {e(A,B,f)} = \sum_{A,B} e(A,B,f) \cdot p(A,B)
%\end{equation}
%
%Clearly, the truncated multipliers in case fixed non-uniform distribution is just a specific case of this problem, in which the solution is optimal system $h^*(p)$. In general, we don't know prior distribution p, we need to find the minimax robust multipliers $h_R$ such that:
%
%\begin{equation}
%h_R \in arg \min_{h \in H} \max_{p \in P} M(h, p)
%\end{equation}
%
%This is nested optimization problems (an optimization is embedded in another optimization).
%\newdef{solution}{Solution}
%\begin{solution}
%We first try to solve for the worst distribution:
%\[
%M(h, p*(h)) = M^*(h) = \max_{p \in P} M(h,p)
%\]
%
%Since (1), it's not too hard to see that, given h, $M(h,p)$ reaches maximum when the maximum errors have the highest probability as possible. If we don't have any other restriction on distribution p (means it takes any distribution on valid area), the input source has just one signal at which, maximum error occurred.
%
%\begin{equation}
%M^*(h) =  e^*(f)
%\end{equation}
%
%In which, 
%
%\begin{equation}
%e^*(f) = \max_{A,B} e(A, B, f)
%\end{equation}
%
%Figure ? plot $e^*(f)$ with an example interval of f.
%
%(Note for us only: it is extremely similar to the Minimax Binary Hypothesis in Poor's book. The difference is that, in Binary Hypotheis, p is 1 dimension ($\pi$), in this, p is $2^{2(n-1)}$ dimensions.)
%\end{solution}
%
%\begin{solution}
%We need to solve:
%\begin{equation}
%h_R \in arg \min_f e^*(f)
%\end{equation}
%
%To solve this, we first notice that we can bound f to an interval related to the size of input numbers and truncated columns.
%
%Second, after bounding f, we use line search techniques to search for the minimum values.
%
%(under construction)
%\end{solution}

\section{Experimental Results}
(in designing)
\section{Discussion}
(later)
\section{Conclusion and Future Work}
(later)
%\section{The {\secit Body} of The Paper}
%Typically, the body of a paper is organized
%into a hierarchical structure, with numbered or unnumbered
%headings for sections, subsections, sub-subsections, and even
%smaller sections.  The command \texttt{{\char'134}section} that
%precedes this paragraph is part of such a
%hierarchy.\footnote{This is the second footnote.  It
%starts a series of three footnotes that add nothing
%informational, but just give an idea of how footnotes work
%and look. It is a wordy one, just so you see
%how a longish one plays out.} \LaTeX\ handles the numbering
%and placement of these headings for you, when you use
%the appropriate heading commands around the titles
%of the headings.  If you want a sub-subsection or
%smaller part to be unnumbered in your output, simply append an
%asterisk to the command name.  Examples of both
%numbered and unnumbered headings will appear throughout the
%balance of this sample document.
%
%Because the entire article is contained in
%the \textbf{document} environment, you can indicate the
%start of a new paragraph with a blank line in your
%input file; that is why this sentence forms a separate paragraph.
%
%\subsection{Type Changes and {\subsecit Special} Characters}
%We have already seen several typeface changes in this sample.  You
%can indicate italicized words or phrases in your text with
%the command \texttt{{\char'134}textit}; emboldening with the
%command \texttt{{\char'134}textbf}
%and typewriter-style (for instance, for computer code) with
%\texttt{{\char'134}texttt}.  But remember, you do not
%have to indicate typestyle changes when such changes are
%part of the \textit{structural} elements of your
%article; for instance, the heading of this subsection will
%be in a sans serif\footnote{A third footnote, here.
%Let's make this a rather short one to
%see how it looks.} typeface, but that is handled by the
%document class file. Take care with the use
%of\footnote{A fourth, and last, footnote.}
%the curly braces in typeface changes; they mark
%the beginning and end of
%the text that is to be in the different typeface.
%
%You can use whatever symbols, accented characters, or
%non-English characters you need anywhere in your document;
%you can find a complete list of what is
%available in the \textit{\LaTeX\
%User's Guide}\cite{Lamport:LaTeX}.
%
%\subsection{Math Equations}
%You may want to display math equations in three distinct styles:
%inline, numbered or non-numbered display.  Each of
%the three are discussed in the next sections.
%
%\subsubsection{Inline (In-text) Equations}
%A formula that appears in the running text is called an
%inline or in-text formula.  It is produced by the
%\textbf{math} environment, which can be
%invoked with the usual \texttt{{\char'134}begin. . .{\char'134}end}
%construction or with the short form \texttt{\$. . .\$}. You
%can use any of the symbols and structures,
%from $\alpha$ to $\omega$, available in
%\LaTeX\cite{Lamport:LaTeX}; this section will simply show a
%few examples of in-text equations in context. Notice how
%this equation: \begin{math}\lim_{n\rightarrow \infty}x=0\end{math},
%set here in in-line math style, looks slightly different when
%set in display style.  (See next section).
%
%\subsubsection{Display Equations}
%A numbered display equation -- one set off by vertical space
%from the text and centered horizontally -- is produced
%by the \textbf{equation} environment. An unnumbered display
%equation is produced by the \textbf{displaymath} environment.
%
%Again, in either environment, you can use any of the symbols
%and structures available in \LaTeX; this section will just
%give a couple of examples of display equations in context.
%First, consider the equation, shown as an inline equation above:
%\begin{equation}\lim_{n\rightarrow \infty}x=0\end{equation}
%Notice how it is formatted somewhat differently in
%the \textbf{displaymath}
%environment.  Now, we'll enter an unnumbered equation:
%\begin{displaymath}\sum_{i=0}^{\infty} x + 1\end{displaymath}
%and follow it with another numbered equation:
%\begin{equation}\sum_{i=0}^{\infty}x_i=\int_{0}^{\pi+2} f\end{equation}
%just to demonstrate \LaTeX's able handling of numbering.
%
%\subsection{Citations}
%Citations to articles \cite{bowman:reasoning,
%clark:pct, braams:babel, herlihy:methodology},
%conference proceedings \cite{clark:pct} or
%books \cite{salas:calculus, Lamport:LaTeX} listed
%in the Bibliography section of your
%article will occur throughout the text of your article.
%You should use BibTeX to automatically produce this bibliography;
%you simply need to insert one of several citation commands with
%a key of the item cited in the proper location in
%the \texttt{.tex} file \cite{Lamport:LaTeX}.
%The key is a short reference you invent to uniquely
%identify each work; in this sample document, the key is
%the first author's surname and a
%word from the title.  This identifying key is included
%with each item in the \texttt{.bib} file for your article.
%
%The details of the construction of the \texttt{.bib} file
%are beyond the scope of this sample document, but more
%information can be found in the \textit{Author's Guide},
%and exhaustive details in the \textit{\LaTeX\ User's
%Guide}\cite{Lamport:LaTeX}.
%
%This article shows only the plainest form
%of the citation command, using \texttt{{\char'134}cite}.
%This is what is stipulated in the SIGS style specifications.
%No other citation format is endorsed or supported.
%
%\subsection{Tables}
%Because tables cannot be split across pages, the best
%placement for them is typically the top of the page
%nearest their initial cite.  To
%ensure this proper ``floating'' placement of tables, use the
%environment \textbf{table} to enclose the table's contents and
%the table caption.  The contents of the table itself must go
%in the \textbf{tabular} environment, to
%be aligned properly in rows and columns, with the desired
%horizontal and vertical rules.  Again, detailed instructions
%on \textbf{tabular} material
%is found in the \textit{\LaTeX\ User's Guide}.
%
%Immediately following this sentence is the point at which
%Table 1 is included in the input file; compare the
%placement of the table here with the table in the printed
%dvi output of this document.
%
%\begin{table}
%\centering
%\caption{Frequency of Special Characters}
%\begin{tabular}{|c|c|l|} \hline
%Non-English or Math&Frequency&Comments\\ \hline
%\O & 1 in 1,000& For Swedish names\\ \hline
%$\pi$ & 1 in 5& Common in math\\ \hline
%\$ & 4 in 5 & Used in business\\ \hline
%$\Psi^2_1$ & 1 in 40,000& Unexplained usage\\
%\hline\end{tabular}
%\end{table}
%
%To set a wider table, which takes up the whole width of
%the page's live area, use the environment
%\textbf{table*} to enclose the table's contents and
%the table caption.  As with a single-column table, this wide
%table will ``float" to a location deemed more desirable.
%Immediately following this sentence is the point at which
%Table 2 is included in the input file; again, it is
%instructive to compare the placement of the
%table here with the table in the printed dvi
%output of this document.
%
%
%\begin{table*}
%\centering
%\caption{Some Typical Commands}
%\begin{tabular}{|c|c|l|} \hline
%Command&A Number&Comments\\ \hline
%\texttt{{\char'134}alignauthor} & 100& Author alignment\\ \hline
%\texttt{{\char'134}numberofauthors}& 200& Author enumeration\\ \hline
%\texttt{{\char'134}table}& 300 & For tables\\ \hline
%\texttt{{\char'134}table*}& 400& For wider tables\\ \hline\end{tabular}
%\end{table*}
%% end the environment with {table*}, NOTE not {table}!
%
%\subsection{Figures}
%Like tables, figures cannot be split across pages; the
%best placement for them
%is typically the top or the bottom of the page nearest
%their initial cite.  To ensure this proper ``floating'' placement
%of figures, use the environment
%\textbf{figure} to enclose the figure and its caption.
%
%This sample document contains examples of \textbf{.eps}
%and \textbf{.ps} files to be displayable with \LaTeX.  More
%details on each of these is found in the \textit{Author's Guide}.
%
%\begin{figure}
%\centering
%\epsfig{file=fly.eps}
%\caption{A sample black and white graphic (.eps format).}
%\end{figure}
%
%\begin{figure}
%\centering
%\epsfig{file=fly.eps, height=1in, width=1in}
%\caption{A sample black and white graphic (.eps format)
%that has been resized with the \texttt{epsfig} command.}
%\end{figure}
%
%
%As was the case with tables, you may want a figure
%that spans two columns.  To do this, and still to
%ensure proper ``floating'' placement of tables, use the environment
%\textbf{figure*} to enclose the figure and its caption.
%and don't forget to end the environment with
%{figure*}, not {figure}!
%
%\begin{figure*}
%\centering
%\epsfig{file=flies.eps}
%\caption{A sample black and white graphic (.eps format)
%that needs to span two columns of text.}
%\end{figure*}
%
%Note that either {\textbf{.ps}} or {\textbf{.eps}} formats are
%used; use
%the \texttt{{\char'134}epsfig} or \texttt{{\char'134}psfig}
%commands as appropriate for the different file types.
%
%
%\subsection{Theorem-like Constructs}
%Other common constructs that may occur in your article are
%the forms for logical constructs like theorems, axioms,
%corollaries and proofs.  There are
%two forms, one produced by the
%command \texttt{{\char'134}newtheorem} and the
%other by the command \texttt{{\char'134}newdef}; perhaps
%the clearest and easiest way to distinguish them is
%to compare the two in the output of this sample document:
%
%This uses the \textbf{theorem} environment, created by
%the\linebreak\texttt{{\char'134}newtheorem} command:
%\newtheorem{theorem}{Theorem}
%\begin{theorem}
%Let $f$ be continuous on $[a,b]$.  If $G$ is
%an antiderivative for $f$ on $[a,b]$, then
%\begin{displaymath}\int^b_af(t)dt = G(b) - G(a).\end{displaymath}
%\end{theorem}
%
%The other uses the \textbf{definition} environment, created
%by the \texttt{{\char'134}newdef} command:
%\newdef{definition}{Definition}
%\begin{definition}
%If $z$ is irrational, then by $e^z$ we mean the
%unique number which has
%logarithm $z$: \begin{displaymath}{\log e^z = z}\end{displaymath}
%\end{definition}
%
%Two lists of constructs that use one of these
%forms is given in the
%\textit{Author's  Guidelines}.
% 
%There is one other similar construct environment, which is
%already set up
%for you; i.e. you must \textit{not} use
%a \texttt{{\char'134}newdef} command to
%create it: the \textbf{proof} environment.  Here
%is a example of its use:
%\begin{proof}
%Suppose on the contrary there exists a real number $L$ such that
%\begin{displaymath}
%\lim_{x\rightarrow\infty} \frac{f(x)}{g(x)} = L.
%\end{displaymath}
%Then
%\begin{displaymath}
%l=\lim_{x\rightarrow c} f(x)
%= \lim_{x\rightarrow c}
%\left[ g{x} \cdot \frac{f(x)}{g(x)} \right ]
%= \lim_{x\rightarrow c} g(x) \cdot \lim_{x\rightarrow c}
%\frac{f(x)}{g(x)} = 0\cdot L = 0,
%\end{displaymath}
%which contradicts our assumption that $l\neq 0$.
%\end{proof}
%
%Complete rules about using these environments and using the
%two different creation commands are in the
%\textit{Author's Guide}; please consult it for more
%detailed instructions.  If you need to use another construct,
%not listed therein, which you want to have the same
%formatting as the Theorem
%or the Definition\cite{salas:calculus} shown above,
%use the \texttt{{\char'134}newtheorem} or the
%\texttt{{\char'134}newdef} command,
%respectively, to create it.
%
%\subsection*{A {\secit Caveat} for the \TeX\ Expert}
%Because you have just been given permission to
%use the \texttt{{\char'134}newdef} command to create a
%new form, you might think you can
%use \TeX's \texttt{{\char'134}def} to create a
%new command: \textit{Please refrain from doing this!}
%Remember that your \LaTeX\ source code is primarily intended
%to create camera-ready copy, but may be converted
%to other forms -- e.g. HTML. If you inadvertently omit
%some or all of the \texttt{{\char'134}def}s recompilation will
%be, to say the least, problematic.
%
%\section{Conclusions}
%This paragraph will end the body of this sample document.
%Remember that you might still have Acknowledgments or
%Appendices; brief samples of these
%follow.  There is still the Bibliography to deal with; and
%we will make a disclaimer about that here: with the exception
%of the reference to the \LaTeX\ book, the citations in
%this paper are to articles which have nothing to
%do with the present subject and are used as
%examples only.
%%\end{document}  % This is where a 'short' article might terminate
%
%%ACKNOWLEDGMENTS are optional
%\section{Acknowledgments}
%This section is optional; it is a location for you
%to acknowledge grants, funding, editing assistance and
%what have you.  In the present case, for example, the
%authors would like to thank Gerald Murray of ACM for
%his help in codifying this \textit{Author's Guide}
%and the \textbf{.cls} and \textbf{.tex} files that it describes.

%
% The following two commands are all you need in the
% initial runs of your .tex file to
% produce the bibliography for the citations in your paper.

% You must have a proper ".bib" file
%  and remember to run:
% latex bibtex latex latex
% to resolve all references
%
\bibliographystyle{unsrt}
\bibliography{truncmult}  % sigproc.bib is the name of the Bibliography in this case
% ACM needs 'a single self-contained file'!
%
%APPENDICES are optional
%\balancecolumns
\appendix
\section{Minimax Approach}
In essence, Minimax is an approach to design systems that are robust with respect to uncertainties of inputs; whose main idea is to optimize the worst case scenario \cite{verdu:1983}. Denote H a set of systems needed to be designed, P a set of possible input distribution (uncertainty class). M is the cost/payoff function takes real value:

\[
M: H \times P \rightarrow R
\]
The following definition will be used:
\newdef{definition}{Definition}
\begin{definition}
$h^*(p)$ is an optimal system for p $\in$ P if:
\[
M(h^*(p), p) = M^*(p) = \min_{h \in H} M(h, p)
\]
\end{definition} 

\begin{definition}
$p^*(h)$ is a worst distribution for h $\in$ H if:
\[
M(h, p^*(h)) = M^*(h) = \max_{p \in P} M(h, p)
\]
\end{definition}


\begin{definition}
$h_R$ is a minimax robust system for the model (H, P, M) if
\[
h_R \in arg \min_{h \in H} \max_{p \in P} M(h, p)
\]
\end{definition}
 
The objective of minimax method is to find the minimax robust system $h_R$. A lot of contributions have been done to find the condition of H, P, M in which the robust system exists as well as to find the solution given H, P, M in some specific cases, numerically or analytically \cite{verdu:1983},[], [], [], [].
%%Appendix A
%\section{Headings in Appendices}
%The rules about hierarchical headings discussed above for
%the body of the article are different in the appendices.
%In the \textbf{appendix} environment, the command
%\textbf{section} is used to
%indicate the start of each Appendix, with alphabetic order
%designation (i.e. the first is A, the second B, etc.) and
%a title (if you include one).  So, if you need
%hierarchical structure
%\textit{within} an Appendix, start with \textbf{subsection} as the
%highest level. Here is an outline of the body of this
%document in Appendix-appropriate form:
%\subsection{Introduction}
%\subsection{The Body of the Paper}
%\subsubsection{Type Changes and  Special Characters}
%\subsubsection{Math Equations}
%\paragraph{Inline (In-text) Equations}
%\paragraph{Display Equations}
%\subsubsection{Citations}
%\subsubsection{Tables}
%\subsubsection{Figures}
%\subsubsection{Theorem-like Constructs}
%\subsubsection*{A Caveat for the \TeX\ Expert}
%\subsection{Conclusions}
%\subsection{Acknowledgments}
%\subsection{Additional Authors}
%This section is inserted by \LaTeX; you do not insert it.
%You just add the names and information in the
%\texttt{{\char'134}additionalauthors} command at the start
%of the document.
%\subsection{References}
%Generated by bibtex from your ~.bib file.  Run latex,
%then bibtex, then latex twice (to resolve references)
%to create the ~.bbl file.  Insert that ~.bbl file into
%the .tex source file and comment out
%the command \texttt{{\char'134}thebibliography}.
%% This next section command marks the start of
%% Appendix B, and does not continue the present hierarchy
%\section{More Help for the Hardy}
%The sig-alternate.cls file itself is chock-full of succinct
%and helpful comments.  If you consider yourself a moderately
%experienced to expert user of \LaTeX, you may find reading
%it useful but please remember not to change it.
%%\balancecolumns % GM June 2007
%% That's all folks!

\end{document}
